//
//  Sort.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/9/2.
//

import Foundation

/// 冒泡排序
/// - Parameter array: 数组
/// - Returns: 冒泡排序
func bubbleSort<T>(_ collection: inout T) -> Void where T: MutableCollection, T.Element: Comparable {
    guard collection.count >= 2 else {
        return
    }
    
    for end in collection.indices.reversed() {
        var swapped = false
        var current = collection.startIndex
        while current < end {
            let next = collection.index(after: current)
            if collection[current] > collection[next] {
                collection.swapAt(current, next)
                swapped = true
            }
            current = next
        }
        print(collection)
        if !swapped {
            return
        }
    }
}

func selectionSort<T>(_ collection: inout T) -> Void where T: MutableCollection, T.Element: Comparable {
    guard collection.count >= 2 else {
        return
    }
    for currnt in collection.indices {
        var lowest = currnt
        var other = collection.index(after: currnt)

        while other < collection.endIndex {
            if collection[lowest] > collection[other] {
                lowest = other
            }
            other = collection.index(after: other)
        }
        if lowest != currnt {
            collection.swapAt(lowest, currnt)
        }
        print(collection)
    }
}

func insertionSort<T>(_ collection: inout T) -> Void where T: BidirectionalCollection & MutableCollection, T.Element: Comparable {
    guard collection.count >= 2 else {
        return
    }
    for current in collection.indices {
        var shifting = current
        while shifting > collection.startIndex {
            let previous = collection.index(before: shifting)
            if collection[shifting] < collection[previous] {
                collection.swapAt(shifting, previous)
            } else {
                break
            }
            shifting = previous
        }
        print(collection)
    }
}
